package day04;

public class ArraySeek {
	public static void main(String[] args) {
		int[] arr = { 1, 2, 7, 9, 11, 25, 34, 46, 80 };
		System.out.println(halfSearch(arr, 12));
		System.out.println(getIndex(arr, 10));
	}

	/**
	 * 折半查找法
	 * @param arr
	 * @param key
	 * @return
	 */
	public static int halfSearch(int[] arr, int key) {
		int min = 0, max = arr.length - 1, mid;
		while (max >= min) {
			mid = (max + min) >> 1;
			if (arr[mid] < key) {
				min = mid + 1;
			} else if (arr[mid] > key) {
				max = mid - 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

	/**
	 * 有一个有序的数组，想要将一个元素插入到该数组中， 还要保证该数组是有序的。如何获取该元素在数组中的位置
	 */
	public static int getIndex(int[] arr, int key) {
		int min = 0, max = arr.length - 1, mid;
		while (min <= max) {
			mid = (max + min) >> 1;
			if (arr[mid] < key) {
				min = mid + 1;
			} else if (arr[mid] > key) {
				max = mid - 1;
			} else {
				return mid;
			}
		}
		return min;
	}
}
